package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         96,
		Discription: "求节点值为1-n的所有不同二叉搜索树的总数",
		Level:       2,
		Labels: map[string]int{
			"动态规划":  1,
			"二叉树":   1,
			"二叉搜索树": 1,
		},
	})
}

func NumTrees(n int) int {
	dp := make([]int, n+1)
	//空节点组合数量为1
	dp[0] = 1
	dp[1] = 1
	//遍历节点数量
	for i := 2; i <= n; i++ {
		//移动区间，遍历左节点的组合数量*右节点的组合数量
		for leftLength := 0; leftLength <= i-1; leftLength++ {
			dp[i] += dp[leftLength] * dp[i-leftLength-1]
		}
	}

	return dp[n]
}
